package com.hy.study.practice.linkedlist;

/**
 * 约瑟夫环问题
 */
public class JosephCircle {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.initCircle(5);
        circleSingleLinkedList.show();
        circleSingleLinkedList.get(1,2,5);
    }
}

/**
 * 维护一个环形链表
 */
class CircleSingleLinkedList {
    /**
     * 第一个节点
     */
    private Person first;

    /**
     * 根据约瑟夫环出队
     *
     * @param i 从那个人开始
     * @param k 每次隔几个
     * @param n 总共有多少个
     */
    public void get(int i, int k, int n) {
        if (i < 0 || i > n || k > n || k < 0) {
            System.out.println("输入参数异常");
            return;
        }
        Person helper = first;
        while (helper.getNextPerson()!=first){
            helper=helper.getNextPerson();
        }
        for (int j = 1; j < i; j++) {
            first = first.getNextPerson();
            helper = helper.getNextPerson();
        }
        while (true){
          if(helper==first){
              //最后一个了
              break;
          }else {
              for (int j = 1; j < k; j++) {
                  first = first.getNextPerson();
                  helper = helper.getNextPerson();
              }
              System.out.println("小孩出圈:"+first);
              first=first.getNextPerson();
              helper.setNextPerson(first);
          }
        }
        System.out.println("最后出圈的小孩:"+first);
    }

    /**
     * 初始化一个环形链表
     *
     * @param n 链表的大小
     */
    public void initCircle(int n) {
        if (n < 0) {
            System.out.println("链表大小参数错误");
            return;
        }

        Person temp = null;
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                first = new Person(i, i + "位");
                first.setNextPerson(first);
                temp = first;
            } else {
                Person person = new Person(i, i + "位");
                temp.setNextPerson(person);
                person.setNextPerson(first);
                temp = person;
            }
        }
    }

    /**
     * 展示整个环形链表
     */
    public void show() {

        if (first == null) {
            System.out.println("链表为空!!");
            return;
        }
        Person temp = first;
        while (true) {
            System.out.println(temp);
            temp = temp.getNextPerson();
            if (temp.getNextPerson() == first) {
                break;
            }
        }

    }

}

class Person {
    private int no;
    private String name;
    private Person nextPerson;

    public Person(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Person getNextPerson() {
        return nextPerson;
    }

    public void setNextPerson(Person nextPerson) {
        this.nextPerson = nextPerson;
    }

    @Override
    public String toString() {
        return "Person{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
